package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LeetCodeMain29 {
    public List<Integer> partitionLabels(String s) {
        int[] arr=new int[27];
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);
            arr[ch-'a']=i;
        }
        List<Integer> list=new ArrayList<>();
        int left=0;
        int right=0;
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);
            right=Math.max(right,arr[ch-'a']);
            if (i == right) {
                list.add(right - left + 1);
                left = i + 1;
            }
        }
        return list;
    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]? o1[1]-o2[1]:o1[0]-o2[0];
            }
        });
        List<int[]> list=new ArrayList<>();
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int left=intervals[i][0];
            int right=intervals[i][1];
            int flag=1;
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j)[1]>=right){
                    flag=0;
                    break;
                }else if (list.get(j)[1]>=left&&list.get(j)[1]<right){
                    int[] arr=list.get(j);
                    arr[1]=intervals[i][1];
                    list.remove(j);
                    list.add(j,arr);
                    flag=0;
                    break;
                }
            }
            if (flag!=0){
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[list.size()][2]);
    }
}
